package com.lun.easy;

import java.util.LinkedList;

import com.lun.util.BinaryTree.TreeNode;

public class RangeSumOfBST {
	
	//方法一：遍历所有节点，符合要求进行累加
    public int rangeSumBST(TreeNode root, int low, int high) {
        int[] sum = {0};
    	inorderTraverse(root, low, high, sum);
    	return sum[0];
    }
    
    private void inorderTraverse(TreeNode node, int low, int high, int[] sum) {
    	if(node == null) 
    		return;
    	
    	inorderTraverse(node.left, low, high, sum);
    	
    	if(low <= node.val && node.val <= high)
    		sum[0] += node.val;
    	
    	inorderTraverse(node.right, low, high, sum);
    }
    
    //方法二：递归版
    public int rangeSumBST2(TreeNode root, int L, int R) {
        if (root == null) return 0; // base case.
        if (root.val < L) return rangeSumBST(root.right, L, R); // left branch excluded.
        if (root.val > R) return rangeSumBST(root.left, L, R); // right branch excluded.
        //剩下的就是 L <= root.val && root.val <= R
        return root.val + rangeSumBST(root.right, L, R) + rangeSumBST(root.left, L, R); // count in both children.
    }
    
    //方法三：迭代法
    public int rangeSumBST3(TreeNode root, int L, int R) {
        LinkedList<TreeNode> stk = new LinkedList<>();
        stk.push(root);
        int sum = 0;
        while (!stk.isEmpty()) {
            TreeNode n = stk.pop();
            if (n == null) { continue; }
            if (n.val > L) { stk.push(n.left); } // left child is a possible candidate.
            if (n.val < R) { stk.push(n.right); } // right child is a possible candidate.
            if (L <= n.val && n.val <= R) { sum += n.val; }
        }
        return sum;
    }
    
}
